Programming languages can be viewed as belonging to one of three levels: low, middle, and high. One example of a low-level programming language is assembly language, which is a mnemonic representation of machine language intended to be understandable by humans. In contrast, a high-level programming language such as Java uses syntax and concepts that more closely align with human reasoning. A high-level programming language also provides high levels of run-time access security and memory protection at the expense of some program execution speed. “Mid-level” programming languages, as used herein, have some of the “look and feel” of high-level programming languages in that, in comparison to low level languages, they appear and read in a fashion more similar to ordinary human reasoning. Mid-level programming languages allow a programmer to directly manipulate and access memory addresses, and as such, they are more computationally efficient than high level languages. In other words, for improved execution speed, mid-level programming languages omit the run-time memory access checks that a high level language might perform. Such languages may also allow direct access to memory for driving hardware devices that have control registers at fixed addresses. However, mid-level programming languages allow a program to access an illegal memory address, and as such, are often dangerous. The illegal memory accesses sometimes occur without the detection of any error at the time. Potential consequences include subsequent unpredictable behavior, and accumulated errors that result in an illegal operation and the termination of the program.
Examples of mid-level programming languages are C and C++. The version of the C language familiar to most C programmers at present is the ANSI 1989 C programming language referred herein as C89, that has the mid-level features discussed above. C++ is an object-oriented version of C89. As used herein, the term C99 refers to the publication: International Standard ISO/IEC 9899:1999(E) Programming Languages—C. As an improvement on the C89 standard, the C99 standard is used throughout this specification to illustrate examples of the possible logical mistakes, dangers, and limitations associated with mid-level programming languages, particularly with respect to the way in which mid-level programming languages handle arrays.
Since this application includes programming terms, some of these terms are introduced and defined below. These definitions are intended to assist the reader with understanding the description contained herein. Unless otherwise stated, these definitions are not intended to override the ordinary meaning that one of ordinary skill in the art would give them upon reading this description and the appended claims.
A language is defined by a grammar, such as the rules that define good sentence structures in spoken languages. Programming languages are used to express a program as text—usually contained in files. Files can be translated into low-level machine code or assembler for a target computer type by a computer program called a compiler. A cross compiler is a compiler that runs on one computer and produces machine code targeted for a different type of computer. A native compiler runs on the target computer or a computer of the same type. The resulting low-level machine code is placed in an executable file. The file can be loaded into memory to run on the target computer.
A compiler will not compile programs that do not comply with its grammar, which is the basis for programming language definitions. Some aspects of a programming language are lexical or word-based. For example, certain keywords are used to express certain language ideas and instructions, similar to verbs. Special characters or character groupings like ‘=’ or ‘+=’ or ‘;’ have properties similar to keywords. Identifiers are similar to nouns, and can take any alphanumeric name, excluding spaces, which allows complicated names to be used.
When defining the syntax of a grammar, the use of angle brackets like <numeric_expression> or <file_name> for example, indicates any text that matches the named type. Comments appear after //, and remain comments until the end of the line of text. A simple syntax is defined by the following example:
<variable_identifier>=<numeric_expression>; // assign value to variable Variable names are types of identifiers that can hold values. For example, the syntax above matches only the first two lines of text below:
my_value = 1 + 3;// match: left side is variable, right is numericconstantcounter = 4.3;// match as abovea + b = 3;// no match as a + b is not an identifier.The compiler itself can perform some compile-time calculations on a program, such as evaluating constant numeric expressions. Other calculations depend on input to the compiled program when it is running. These calculations are run-time calculations, which are performed when the compiled program is running on a computer.
An array is an arrangement of information in one or more dimensions, such as a 1-dimensional list, or a color component of a 2-dimensional image. Multi-dimensional arrays are those with two dimensions or higher. The individual data items in the array are called elements. All elements in the array are of the same data type; and therefore all elements in the array are also the same size. The array elements are often stored contiguously in the computer's memory, and the subscript or index of the first element is normally zero in all the dimensions applied to the array. The array name, the element data type, the number of array dimensions, and the size of each dimension are all declared in some manner. Each occurrence of the array name in a program is an array identifier. The element data type also can yield the element size.
A pointer is a reference to an address in the computer memory. De-referencing a pointer provides access to the data in the memory that it points to, either to read the memory data, or over-write it with new data. An array identifier contains a pointer to the base address of the array in memory. The base address is the memory address of the first element in the array.
Processors are used in many different environments. For example, processors are used to perform the central processing tasks in a general-purpose computer, and are used to perform the more dedicated processing tasks of a device embedded in an appliance. A processor is a device that is programmed to execute a sequence of machine instructions stored in memory. Two characteristics that distinguish processors include the set of tasks they are expected to perform, and the speed at which they execute the tasks.
Digital Signal Processing (DSP) is a common term used to describe algorithms or special sequences of arithmetic operations on data to perform various functions. This data is usually represented in arrays. Typical examples include motion estimation, data compression and decompression, filtering, and re-sampling. DSP tasks are relatively easily described in a software program that is compiled to run on a processor. In comparison to a dedicated hardware design, processors provide flexibility as they facilitate algorithm changes.
In most DSP applications, the size of arrays can only be established at run-time. The C89 standard does not support run-time variable-length multi-dimensional arrays, making DSP coding difficult in the C language. The C99 standard addresses this shortcoming by including support for variable-length automatic arrays. C99 also includes the ability to declare arrays anywhere in the code, and to declare arrays of any number of dimensions and size, using expressions for each dimension that can be evaluated at run-time. The compiler generates machine code to allocate memory to store array elements before the elements are accessed. At the machine level, memory allocation usually occurs in units of bytes. A byte is the smallest processor-addressable unit in memory, which usually is 8 bits. The amount of memory allocated in bytes is equal to the total number of array elements multiplied by the element size in bytes. The compiler must also generate machine code to allow array element access, so that a processor can read or write data into array elements.
Subroutines are, as their name suggests, routines or functions that are called from another routine. A routine often calls subroutines to reduce its own complexity and enhance its effectiveness. In fact, almost all routines are called, and they are therefore subroutines too. Useful subroutines tend to encapsulate or embody a useful programming concept into a single re-usable block of code. Subroutines can be designed to be re-usable in many different situations, and they may be called from many different places.
Automatic storage is declared storage that is only available after its declaration, and only within the scope of a block of statements in which it is declared. The storage is released when code execution leaves the block.
The heap represents a pool of available memory that is usable by programs running on a computer. Subroutines are used in C to dynamically allocate a contiguous region of memory and free it after it is no longer needed. For example, C code syntax such as:<identifier>=malloc(<nr_of_items_requested>*sizeof(<element_type>))andfree(<identifier>)is often used. The sizeof(<element_type>) expression obtains the size of each array element in bytes from the element type. The malloc( ) function requests memory in byte quantities at run-time. The malloc( ) return value is a pointer to the allocated memory base address. This value is stored for use as a handle to the allocated memory. The memory is dynamically allocated. In other words, at run-time, an amount of memory is requested and then allocated. A handle is a value that can be used to selectively access an object as a whole (in this case, the object is the allocated memory). A handle is usually a pointer into memory that is used to select an object as a whole. In this case, the handle can be given to free( ) to free the dynamically allocated memory resource. In C, this value is also a pointer, but given its other role, it is preferable that a handle should not be modified using pointer arithmetic. The handle value could be modified and restored, but this practice is dangerous in mid-level languages, and not even allowed in high level languages.
The new C99 standard provides variable length array support so that as far as the programmer is concerned, the malloc( ) and free( ) calls are not explicitly required for dynamically allocated array element storage. This is very different from the C89 standard which required these functions for variable sized arrays. For example, in C99, a two-dimensional array can be declared using:<element_type><array_identifier>[<height_expr>][<width_expr>]wherein <width_expr> or <height_expr> use expressions that must each evaluate to an integer at run-time. The underlying implementation of array element storage allocation in variable length arrays by the C99 compiler is not defined. Array element storage allocation in a typical compiler may therefore use the malloc( ) and free( ) functions, as these functions are generic and commonly available. A C99 variable length array declaration can occur anywhere within a block of program statements in a subroutine prior to use. The scope of the array is automatic, i.e. array access is limited to within the block of statements in which it is declared. For example, array element writes to the two-dimensional array declared above can use assignment statement syntax of the form:<array_identifier>[<row_index>][<column_index>]=<expression>.Array elements can also be read as a value in expressions.
By convention, major dimensions represent array sizes or access indices in higher dimensions. The most major dimension is represented as the left-most term in square brackets following an array identifier. In contrast, minor dimensions represent lower-dimensional array sizes or access indices to the right. The <row_index> is major in the array access expression above, and the column index is minor. In the C language, according to the two-dimensional array declaration and access above, the values of <row_index> should be in the inclusive range 0 to <height_expr>−1, i.e. the most major index should comply with the size of the corresponding most major dimension size in the array, and so on down the more minor indices. If the number of indices applied to an array exceeds the declared array dimensionality then the remaining “unused” indices are applied to the array element by the compiler. This implies that the array elements must be arrays themselves in this case. If not (that is, all the indices cannot be used up), then there is a programming error. If the number of indices is less than the declared dimensionality, then the elements are arrays themselves, with sizes corresponding to the remaining unused declared minor sizes.
In hardware, memory is accessed as one-dimensional contiguous storage that is indexed by the memory address. In C, a base address is provided for an allocated region of memory, and then one-dimensional array access can be achieved by adding an index offset (scaled by the array element size) to the base address. If the base address is a memory pointer referenced by an array identifier in the C code, and if the type of data pointed to by the pointer is declared as the array element type, then the size of the elements are known at compile time. This allows the compiler to generate machine code to allow array elements to be accessed using a one-dimensional index without knowing anything about the size of the array.
An array base address passed down to a subroutine may actually have various attributes, such as its base address, and the number and size of its dimensions. The C99 standard treats array references as base addresses, so a compiler only knows about array attributes from their declarations within the scope of a block. In the C language, each subroutine can be separately compiled, so if a subroutine calls another and passes an array reference, a simple base address cannot contain array attribute information. The C language allows the definition and use of structures, which are aggregates of data. Members of the structure are accessed using the syntax <structure_reference>→<member>. Structures can be defined to include array attribute information, but only a reference to a member of a structure can obtain the array base address. For example, array→base_address[row][column] can be indexed. This syntax is cumbersome.
C99 declared arrays are either implemented as arrays of arrays, or by using index mapping expressions. In either case, multi-dimensional array access is slow. The array-of-arrays implementation uses a one-dimensional array to store references to other base addresses of sub-arrays in memory. Each sub-array may contain references to other arrays, etc. The number of array dimensions defines the number of one-dimensional array accesses required to obtain the desired array element. The index mapping approach performs calculations on sets of indices to map them onto an equivalent single index used to access an element from the one-dimensional array memory. In this case, an additional multiply is required for each additional array dimension.
To improve the execution speed of compiled C programs (or any mid-level programming language), index ranges are not automatically checked at compile-time or run-time. If out-of-bounds array indices are used, the underlying array access mechanism may access memory outside that allocated for the array, possibly causing a running program to terminate.
Many C programmers try to improve program speed in C by recognizing that for many algorithms, array elements are often accessed sequentially. Therefore memory access patterns such as: write to A[0][0], write to A[0][1], write to A[0][2] . . . are common. Programmers may write code to avoid indexing altogether, and instead use pointer arithmetic. For example, the code A[0]=1; A[1]=2; A[2]=3; . . . can be replaced by A[0]=1; A=A+1; A[0]=2; A=A+1; A[0]=3; A=A+1; etc. In other words, the memory pointed to by A is repeatedly written to, and then the pointer A itself is changed. The cumulative changes to the pointer A must be correct for the code to operate correctly, otherwise A may point outside of the original array bounds.
Since execution speed is important within a DSP environment, mid-level languages like C are often used with pointer arithmetic. The result is code that is complex and fragile, as it relies on the correct accumulation of address calculations throughout the entire program. Also, using pointer arithmetic makes programs harder to understand and maintain, because valid pointer de-referencing depends on correct prior address calculations. These calculations could be spread out in the program, so they have to be understood over a large scope before each instance of a de-reference can be understood.
Many programmers have to deal with legacy code. They may have to write new code to replace a lower level subroutine, and deal with pointers to arrays as inputs to the subroutine. It would be helpful if the programmer could access the memory as an array, rather than using pointer arithmetic. The C99 standard supports declaring a variable size array input to a subroutine, but it does not support the use of general expressions for array sizes within declarations. In many situations, legacy code may pass down an array base address, and other array information that is used by a subroutine to perform various array-based tasks. There is a requirement to be able to access this data using an array view based on calculations on the passed parameters. The C99 standard allows an array declaration within a subroutine declaration, and the number and size of array dimensions can be a direct function of the input parameters. However, insertion of non-trivial code in a declaration is not possible, thus limiting its use. In addition, as there is no way to release the view and impose new views within the scope of the subroutine.
Many DSP applications generate an output image based on a source or input image. Information outside of the bounds of the input image is often required to properly generate the output image. For example, digital filters may take several input array elements to generate an output array element. The input elements used are usually clustered around the output element if one visualizes the input and output arrays as superimposed images.
If an output element is at the edge of the output array, then input elements needed to calculate its value may lie beyond the edge of the input array. DSP programmers make decisions about how to treat out-of-bounds indexing, but then they write obscure code to control the behavior of their program at the edges of the source or input image. The intentions of boundary handling code are often not explicit, and the code tends to be very complex and error-prone, particularly when pointer arithmetic and multi-dimensional arrays are being used together.
Therefore, there is a need in the art to provide a system and method that overcomes these problems by including language features that allow programmers to use array indexing schemes instead of pointer arithmetic in both new and legacy code, and allowing the programmer to simply and explicitly specify array access behavior for invalid array access indices.